package org.basis.algorithm.tree;

import org.basis.algorithm.tree.common.Node;

import java.util.LinkedList;

/**
 * 完全二叉树检查
 * 完全二叉树定义：从左到右依次变满的二叉树，隐藏着判断规则就是：
 * ①、宽度优先遍历树，遇到第一个左右孩子不双全的节点后，后面的其他节点都应该是叶子节点
 * ②、如果有左右孩子不双全的节点，那么该节点要么没有孩子，要么只有左孩子
 *
 * @author Mr_wenpan@163.com 2021/12/22 11:22
 */
public class CheckCompleteBinaryTree {

    public static void main(String[] args) {

    }

    public static boolean isCbt(Node head) {
        if (head == null) {
            return true;
        }
        LinkedList<Node> queue = new LinkedList<>();
        queue.add(head);
        boolean isLeaf = false;
        while (!queue.isEmpty()) {
            Node poll = queue.poll();
            if (poll.left == null || poll.right == null) {
                // 遇到左右孩子不双全的情况，但却是只有右孩子的情况直接返回false
                if (poll.right != null) {
                    return false;
                }
                isLeaf = true;
            }
            // 已经遇到左右孩子不双全的情况下，如果后面的节点还有孩子，则false
            if (isLeaf && (poll.left != null || poll.right != null)) {
                return false;
            }
            if (poll.left != null) {
                queue.add(poll.left);
            }
            if (poll.right != null) {
                queue.add(poll.right);
            }
        }
        return true;
    }
}
